The invention relates to a method according to the preamble of Claim 1. Encrypting by executing a standardized modular exponentiation is used in the environment of a smart card and elsewhere, such as for supporting financial operations, through blocking opportunity for falsifying the control or contents of such operations. Encryption can be expressed as y= less than xe greater than M, wherein x is a message, e is an encryption key, and M a modulus. Likewise, decryption is effected as D(y)= less than yd greater than M, wherein d is the decryption key, and retrieving x from D is straightforward. For a particular device, the values of M and e are known and fixed, the content of x to be encrypted is naturally unknown and variable, and the value of d is fixed but unknown. For certain operations, such as the providing of an encoded signature, the first encoding also operates with a secret key along similar lines. For the present description, such encoding is also called xe2x80x9cdecryptingxe2x80x9d. Now, the decrypting is effected digit-wise. For each digit of D, one or two first multiplications X*Y mod M produce a first result. The attaining of such first result is followed by an addition. After attaining a second result, the next digit of D is processed. Prior technology has kept the size of the second result down by, in operation, subtracting an appropriate multiplicity (zero, one, or more) of the quantity M, because the register width of available hardware is adapted to the digit length, that is generally much less than the size of the overall quantities used in the multiplication.
It has been found that the sequential pattern of the above multiplicity may depend on the values of X, Y, and M. Further, the use of temporal statistics on a great number of mutually unrelated decryption operations with arbitrary messages allows to derive a value for d. This renders the protection by the encryption illusory. Therefore, a need exists to mask these statistical variations by some additional affecting of the calculation procedure.
In consequence, amongst other things, it is an object of the present invention to suppress the relation between the value of the decryption key and the temporal structure of the calculating steps, through a masking mechanism that does not appreciably lengthen the calculations, nor would necessitate inordinate hardware facilities. Now therefore, according to one of its aspects, the invention is characterized by the characterizing part of Claim 1. In particular, the inventors have recognized that present day microcontrollers, even those that are used in the constraining environment of a smart card, can allow the use of longer storage registers than before, and in particular, a few bits longer than the digits used in the calculation. Such registers would provide the extra freedom that the present invention is in need of.
Advantageously, the procedure executes the exponentiation along the Quisquater or Barrett prescriptions. These are methods commonly in use, and the amending of their prosecution for adhering to the invention is minimal. The pattern of the calculation procedure no longer depends on the decryption key. This takes away any method for so deciphering the value of the decrypting key.
The invention also relates to a device arranged to implement the method of the invention. Further advantageous aspects of the invention are recited in dependent Claims.